#pragma once
#include<bitset>
using namespace std;

template<class k>
class BKDRHash
{
public:
	unsigned int operator()(const k& key)
	{
		unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
		unsigned int hash = 0;

		for (auto ch : key)
		{
			hash = hash * seed + ch;
		}

		return (hash & 0x7FFFFFFF);
	}
};

template<class k>
class DJBHash
{
public:
	unsigned int operator()(const k& key)
	{
		unsigned int hash = 5381;

		for(auto e : key)
		{
			hash += (hash << 5) + e;
		}

		return (hash & 0x7FFFFFFF);
	}
};

template<class k>
class SDBMHash
{
public:
	unsigned int operator()(const k& key)
	{
		unsigned int hash = 0;

		for(auto ch : key)
		{
			// equivalent to: hash = 65599*hash + (*str++);
			hash = ch + (hash << 6) + (hash << 16) - hash;
		}

		return (hash & 0x7FFFFFFF);
	}
};

template<size_t N, class k = string, 
	class HushFuc1 = BKDRHash<k>,
	class HushFuc2 = DJBHash<k>,
	class HushFuc3 = SDBMHash<k>>
class bloom_filter
{
public:
	void Set(const k& key)
	{
		int hush1 = HushFuc1()(key) % N;
		int hush2 = HushFuc2()(key) % N;
		int hush3 = HushFuc3()(key) % N;
		
		_s.set(hush1);
		_s.set(hush2);
		_s.set(hush3);
	}

	bool test(const k& key)
	{
		int hush1 = HushFuc1()(key) % N;
		if (!_s.test(hush1)) return false;

		int hush2 = HushFuc2()(key) % N;
		if (!_s.test(hush2)) return false;

		int hush3 = HushFuc3()(key) % N;
		if (!_s.test(hush3)) return false;
		return true;
	}

private:
	bitset<N> _s;
};